package com.wenmingliang.ch01;

/**
 * @author wenmingliang
 * @create 2023/4/6
 */
public class BinarySearch {

    /**
     *  二分查找基础版代码实现:
     *     返回目标值target的下标index
     */

    public static int findValueIndex1(int arr[], int target) {

        int i = 0, j = arr.length - 1;
        int mid,index = -1;

        while (i <= j) {
            /**
             * 本质上这个操作是有问题的，mid 过大时可能超出整型范围（会把最高位当成符号位）， 由于Java中把二进制的最高位看成是符号位，
             * 所以在Java里同样一个二进制数可能表现出不同的数
             */
            mid = (i + j) / 2;
            if (target < arr[mid]) {
                j = mid - 1;
            }
            if (target > arr[mid]) {
                i = mid + 1;
            }
            if (target == arr[mid]){
                index = mid;
                return index;
            }
        }

        return index;
    }

    /**
     *  二分查找升级版代码实现:
     *     返回目标值target的下标index
     *     返回值：
     *         -1   失败
     *         大于等于0  成功
     */

    public static int findValueIndex2(int arr[], int target) {

        int i = 0, j = arr.length - 1;
        int mid,index = -1;

        while (i <= j) {
            mid = (i + j) >>> 1;   // 右移一位
            if (target < arr[mid]) {
                j = mid - 1;
            }
            if (target > arr[mid]) {
                i = mid + 1;
            }
            if (target == arr[mid]){
                index = mid;
                return index;
            }
        }

        return index;
    }

    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5};
        int target = 5;
        System.out.println(findValueIndex1(arr, target));
        System.out.println(findValueIndex2(arr, target));
    }
}
